La construction classique des nombres entiers naturels résulte des axiomes de Peano. cf Les entiers de Peano et les autres

En revanche, celle des ordinaux est basée sur les relations d'ordre, et plus particulièrement sur les bons ordres. cf Les ordinaux (page web en pdf)

La ressemblance la plus frappante entre les deux est que tout les entiers naturels, ainsi que les ordinaux, ont un successeur.

Mais une différence essentielle entre entiers naturels et ordinaux est que selon Peano, tous les entiers naturels sauf 0 ont un prédécesseur : (axiome 2 de Peano : ), alors que certains ordinaux transfinis comme n'ont pas de prédécesseur.

Et je me demande si certain très grands entiers comme le nombre de Graham, ou TREE(3), ou Ackerman(999), ou BB(99) ne sont pas dans ce cas. (ce qui imposerait de modifier légèrement les axiomes de Peano, mais pourquoi pas ?) En effet comment définir leur prédécesseur sans utiliser la définition de la fonction qui les a créé, ni bien sûr la soustraction de 1 ?

Mon idée est qu'il semble impossible de trouver un prédécesseur pour ces nombres singuliers sans faire appel à leur propre définition.

Ce sont des (très grands) nombres entiers qui ne sont pas aléatoires, et mème des nombres dont la complexité de Kolmogorov est très inférieure à leur propre valeur. On pourrait dire qu'ils sont anti-aléatoires.

Pour l'instant, nous ne donnons pas de définition formelle de ces nombres, ni de ce que nous entendons par complexité. Nous admettrons seulement que pour tout nombre, on peut trouver sa complexité.

Etant donné l'un de ces nombres, disons , de complexité , on peut utiliser les axiomes de Peano pour construire n+1, n+2, et même une infinité dénombrable d'autres nombres, mais nous nous limiterons à ceux que l'on peut construire par des fonctions qui n'utilisent dans leur définition (ou le programme qui permet de de les construire) que des entiers de complexité strictement inférieure à . On dira que ces nouveaux nombres sont issus de .

Ainsi les nombres singuliers , tout comme le nombre 1, sont à la racine d'une infinité dénombrable d'autres nombres issus de . L'ensemble des entiers ressemblerait donc à un arbre fractal: dont les "noeuds" A,B,C,D...) seraient singuliers.

Une question naturelle qui se pose est : est-ce que cet arbre est vraiment connexe ? Il se pourrait en effet qu'il soit impossible d'atteindre (ou construire) certains nombres singuliers en n'utilisant pour ce faire que des nombres de complexité inférieure. ces nombres n'auraient donc pas de prédécesseur, ils seraient isolés.

Certains des "nœuds" de l'arbre ci-dessus ne seraient donc pas reliés au "tronc" principal !

D'où une troublante ressemblance avec les ordinaux transfinis, (les nœuds seraient donc des ordinaux limite), ainsi qu'avec les réels infinitésimaux, ou les nombres surréels de Conway.

Je pense que oui. Par exemple les busy beavers ("Castors affairés" en français).

Problème : le castor affairé BB(n) n'est pas en général calculable...

Même sans utiliser les machine de Turing, on peut imaginer un langage de programmation capable de manipuler des nombres arbitrairement grands. Dans ce langage, on définit une classe de fonctions prenant en argument une liste de nombres et renvoyant un autre nombre, et telles que :

En fait on peut définir toute une une hiérarchie de fonctions à croissance rapide : cf Hiérarchie de croissance rapide (page wikipedia)

Je pense que la definition correcte des entiers naturels (aux détails techniques près, que nous verront plus loin) doit résulter du fait que tout entier doit pouvoir être écrit par un programme de longueur inférieure à cet entier (ou à son nombre de chiffres, si l'on utilise une autre base que la base unaire)

Sinon, le serpent se mort la queue. Après tout, Peano suggère de construire les entiers un par un à partir de zéro, en utilisant la fonction successeur. Pourquoi ne pas construire au contraire les entiers en tant que résultats de programmes de longueur croissante ?

Je pense cependant qu'une définition correcte des entiers doit utiliser les fonctions à croissance rapide, et que si on ne les utilise pas, alors la plupart des très grands entiers sont "inatteignables" et ne pourraient être produits que par un programme plus long que l'entier lui-même (autrement dit, ils sont aléatoires).

Mais pour moi, ces entiers inatteignables n'existent tout simplement pas.

Je pense aussi que, étant donné deux nombres entiers, il doit être possible de les comparer sans pour cela être obligé de les écrire dans une base quelconque et de procéder à une soustraction, puis une comparaison à zéro. Donc pour chaque couple d'entier il doit exister un algorithme de comparison qui n'utilise pas beaucoup plus de mémoire que le nombre de chiffres total de ces entiers.

Or c'est loin d'être évident si ces deux entiers sont singuliers. Lequel est le plus grand, du nombre de Graham ou de ackerman(ackerman(999)) ?

On va considérer ici uniquement des machines de Turing sur l'aphabet et des nombres qui seront écrits ou lus en unaire par ces machines. (par exemple "1111" pour 4).

Les instructions élémentaires de ces machine seront de la forme (symbole à écrire, direction, état suivant)

Comme le tableau d'instruction de ces machines comporte deux colonnes, une pour "0 lu" et une pour "1 lu", le nombre d'instructions élémentaires pour une machine à états est au plus . On comptera caractérisera la machine par ce nombre d'istructions élémentaires effectivement utilisés par la machine, que l'on appellera des demi-états.

Cette notion "d'atteignabilité" sera utile pour définir une nouvelle version de la fonction "successeur" de Peano.

Ainsi, "1" est 1-atteignable à partir de 0, et 2 est 2-atteignable à partir de 1. En fait, à partir de n'importe quel nombre , le nombre est 2-atteignable par la machine suivante :

Il est intéressant de voir que le nombre 0 est également 2-atteignable à partir de n'importe quel nombre par la machine suivant, qui efface tout simplement le nombre :

C'est ennuyeux car le premier axiome de Peano nous dit que 0 ne peut avoir de prédécesseur.

Cependant si l'on exige en outre que, après avoir rendu son résultat, la machine laisse la tête sur le 1 le plus à gauche de ce résultat ?

A suivre ! #TBC

Les entiers de Peano et les autres